package algorithm.binaryTree;

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    /***** 解法一，回溯算法思路 *****/
    class SolutionA104 {

        int depth = 0;
        int res = 0;

        public int maxDepth(TreeNode root) {
            traverse(root);
            return res;
        }

        // 遍历二叉树
        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }

            // 前序遍历位置
            depth++;
            // 遍历的过程中记录最大深度
            res = Math.max(res, depth);
            traverse(root.left);
            traverse(root.right);
            // 后序遍历位置
            depth--;
        }
    }

    /***** 解法二，动态规划思路 *****/
    class SolutionA104_2 {
        // 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftMax = maxDepth(root.left);
            int rightMax = maxDepth(root.right);
            // 根据左右子树的最大深度推出原二叉树的最大深度
            return 1 + Math.max(leftMax, rightMax);
        }
    }


  // 使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）
    //使用队列,队列来判断根节点的左子树和右子树的内侧和外侧是否相等，
    // 本质是判断两个树是否是相互翻转的

class Solution101_2 {
  // 迭代法，使用普通队列。
  public boolean isSymmetric(TreeNode root) {
      // 来判断根节点的左子树和右子树的内侧和外侧是否相等，
      if (root == null) return false; //节点都没有，肯定不是树了。
      Queue<TreeNode> queue = new LinkedList<>();
      //计划：一次入队俩（左子树和右子树）、并且一次取俩（入队的那两个左右子树）。
      //队列先进先出，所以计划：入队和出队的顺序一样是先左后右。
      queue.offer(root.left);
      queue.offer(root.right);
      //把队列里面的子树全处理完就OK了。
      while (!queue.isEmpty()){
          TreeNode left = queue.poll();
          TreeNode right = queue.poll();

          //一些终止情况：
          if (left == null && right == null){
              continue; // 相等了，节点比较完毕。
          } else if (left !=null && right ==null) {
              return false;
          }else if (left == null && right !=null){
              return false;
          }
          //两者都不为空，则可以继续处理了。
          //处理逻辑：
          if (left.val != right.val) return false;
          //继续判断此节点的左子树和右子树的外侧和内侧是否相等，
          //外侧：左子树 的左VS右子树 的右、 内侧：左子树 的右 VS 右子树 的左。
          queue.offer(left.left);
          queue.offer(right.right);
          queue.offer(left.right);
          queue.offer(right.left);
      }
      //如果一切都正常遍历、执行完。
      return true;
  }
}

class Solution101_1 {
    //递归法：
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return false;
        //调用递归函数，比较左节点，右节点
        boolean res = compare(root.left, root.right);
        return res;
    }
    // 递归遍历判比较左子树和右子树的外侧节点、内侧节点是否相等。
    // 一个树的遍历顺序是中 左右，一个树的遍历顺序是中 右左。
    private boolean compare(TreeNode left, TreeNode right){
        //递归三部曲
        //1 确定递归函数的参数和返回值：参数是左子树节点和右子树节点。
        //2 确定终止条件
        //3 确定单层递归的逻辑

        //递归的终止条件：
        // 1）是节点为空的时候（而不是节点的孩子为空的时候）；
        // 2）是节点不为空：但数值不相同。（节点本身是否相等）
        if (left == null && right ==null){
            return true;
        }else if (left == null && right !=null){
            return false;
        }else if (left != null && right ==null){
            return false;
        }

        if(left.val != right.val) return false;

        //3 确定每层递归的逻辑：
        //比较左子树和右子树的外侧节点 、内侧节点是否相等。
        //外侧：左子树 的左孩子 与 右子树 的右孩子
        //内侧：左子树 的右孩子 与 右子树 的左孩子
        boolean b1 = compare(left.left, right.right);
        boolean b2 = compare(left.right, right.left);
        return b1 && b2;
    }
}


//DFS递归「遍历」的思路
class Solution226 {
  //遍历二叉树的同时把每一个节点的左右孩子翻转一下。
  //前序遍历：中左右
  public TreeNode invertTree(TreeNode root) {
      if (root == null) return root;
      //处理：把每一个节点的左右孩子翻转一下。就是交换它的左右子节点
      TreeNode temp = root.left;
      root.left = root.right;
      root.right = temp;

      invertTree(root.left); //遍历二叉树-左
      invertTree(root.right); //遍历二叉树-右
      return root; //前面的都递归完后才返回
  }
}

//BFS 翻转二叉树
class Solution226BFS {
    //遍历二叉树的同时把每一个节点的左右孩子翻转一下。
    //二叉树的层序遍历——迭代法
    // 一旦出现树的层次遍历，都可以用队列作为辅助结构
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return root;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);// 初始：根节点入队

        while (!queue.isEmpty()) {
            int size = queue.size();  //queue 装了 二叉树的一层。遍历这一层
            while (size > 0) {
                TreeNode node = queue.poll();
                swap(node); // 处理：交换它的左右子节点
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                --size;
            }
        }
        return root;
    }

    private void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}


    // 「分解问题」的思路
    class Solution226_2 {
        // 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            // 利用函数定义，先翻转左右子树
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);

            // 然后交换左右子节点
            root.left = right;
            root.right = left;

            // 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
            return root;
        }
    }

class Solution102_2 {
  //二叉树的层序遍历——DFS--递归方式
    // 用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
  List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {

        // 递归遍历,初始化，传入根节点、与层级
        // 层级（0表示还未处理，+1后是第1层就是在递归的处理逻辑里了）
        traverse(root,0);
        // 递归遍历：一条路走先到底，创建每层的List；再回溯上来，为List填充每层的其他元素。
        // 所以就 正常 递归遍历二叉树：前序遍历：中左右

        return res;
    }

    private void traverse(TreeNode node, Integer level){
        //1、递归参数与返回值：节点与第几层

        //2、递归终止条件：遍历完，node为null
        if(node == null) return;
        //如果不为空，代表这层不是null，而是有元素、需要加level并且加入list
        ++level;

        //3、递归的单层处理逻辑：

        // 递归遍历：一条路走先到底，创建每层的List；再回溯上来，为List填充每层的其他元素。
        // 每层都有1个List，在同一层的加入同一个List。第几层由level标识。

        //先一条路走到底，创建每层的List；
        if(res.size() <level){
            //说明这是个新层级、新层级创建后都要加入结果集res中
            List<Integer> list = new ArrayList<>();
            res.add(list);
        }
        // 再回溯上来，为List填充每层的其他元素。(下标是level -1)
        res.get(level -1).add(node.val);
        // 在 Java 中，基本数据类型是按值传递的，而引用类型传递的就是引用的对象在堆中地址值的拷贝.
        // https://blog.csdn.net/qq_41135605/article/details/109509246

        // 正常 递归遍历二叉树：这里是前序遍历：中左右
        traverse(node.left,level); //此level下，不用--了，都是继承自同一个level
        traverse(node.right,level);
    }
}

//二叉树的最大深度
// 使用递归法的话，分解问题：最大深度可以通过子树的最大深度推导出来。
class Solution104_2 {
    public int maxDepth(TreeNode root) {
        //1、递归的参数与返回值：这个函数的参数与返回值刚好可以
        //2、递归的终止条件
        if(root ==null){
            return 0;
        }
        //3、递归的单层处理逻辑
        //树的最大深度 = 根节点自己 + 左右子树的最大深度的最大值
        int leftMax = maxDepth(root.left);
        int rightMAx = maxDepth(root.right);
        return 1 + Math.max(leftMax,rightMAx);
    }
}

    // 二叉树的最小深度
// 找叶子节点（只有当左右孩子都为空的时候，才说明遍历的最低点了）,
// 应该不需要递归吧，试试：
    //树的最小深度 = 根节点自己 + 左右子树的最小深度的最小值
class Solution111_2 {
    public int minDepth(TreeNode root) {
        //1、递归参数与返回值：ok
        //2、递归终止条件：与 3、与递归的单层处理逻辑
        //终止： 叶子节点 （当然如果 root 首先不为null）
        if (root == null) return 0;
        if(root != null && root.left == null && root.right == null) return 1;
        //1).找叶子节点：左右孩子都为空，直接返回1
        // (上个节点到此叶子节点的距离是1个深度)

        //2).左右孩子有1个为空，返回另一个不为空的节点的深度。
        // 为空节点的那个：递归求得的深度为0
        int leftMin = minDepth(root.left);
        int rightMin = minDepth(root.right);
        // 判断用root.left，root没变、是这个函数中的root
        if(root.left == null) return (1 + rightMin);
        if (root.right == null) return (1+leftMin);
        //第3种情况：左右孩子都不为空，返回左右子树的最小的那个深度
        return 1 + Math.min(leftMin,rightMin);
    }
}
// 完全二叉树的节点个数
class Solution222_2 {
    //迭代法就层次遍历求节点，用队列
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//初始加入根、
        int totalCount =0;

        while (!queue.isEmpty()){
            int size = queue.size();//整个队列里存的就是一层的节点。
            while (size >0){
                TreeNode node = queue.poll();
                totalCount++;
                if (node.left !=null) queue.offer(node.left);//正常的层次遍历
                if (node.right !=null) queue.offer(node.right);
                --size;
            }
        }
        return totalCount;
    }
}

//二叉树的后序遍历
// 迭代法算法思想：
//1、沿着根的左孩子，依次入栈，直到左孩子为空；
//2、读栈顶元素进行判定，若右孩子不空且未被访问，将右孩子执行第一步；
//3、栈顶元素出栈。

class Solution145 {
    public List<Integer> postorderTraversal(TreeNode root) {
        //后序遍历：左右中。
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        //迭代法 用栈实现后序遍历
        // 迭代法算法思想：
        //1、左：从根节点开始，一路向左遍历，直到空；
        //2、右：从栈顶元素开始判定，
        // 若它的右孩子不空且未被访问过，就要遍历它了（左右中，先左）；
        //3、中：否则栈顶元素出栈。（当前根节点已经处理完了、要继续去处理下一个了）

        Stack<TreeNode> stack = new Stack<>();
        // 目标是：root 为空 并且栈为空 表示全遍历了并且都处理过了。否则就处理呗
        TreeNode prev = null;//用于标记是否被访问过
        while (root !=null || !stack.isEmpty()){
            // 左：一路遍历左节点
            while (root !=null){
                stack.push(root);
                root = root.left;
            }
            //从栈里面的最左边开始
            TreeNode node = stack.peek();
            //右：右孩子不空且未被访问过，就需要遍历它了（左右中，先左）；
            if(node.right !=null && node.right != prev){
                root = node.right; // 下次while循环时：让右孩子 一路遍历左节点，入栈
            }else {
                // 右孩子空或被访问过，此节点就遍历完了，就出栈
                //中：
                stack.pop();
                res.add(node.val);
                prev = node; // 标记最近访问结点
                root = null; //表示：此节点不用再入栈遍历了
            }
        }
        return res;
    }
}

//目标：判断它是否是高度平衡的二叉树(左右子树的高度差 <=1)
// 利用后序遍历（迭代法） +求高度的函数（两种方法的实现）
// 必须要后序遍历才能找到深度/高度。
class Solution110_2 {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        //后序遍历：左右中
        //后序遍历（迭代法） ：用栈
        Stack<TreeNode> stack = new Stack<>();//初始化
        TreeNode prev = null;// 标记：被访问过的节点
        //遍历：只要未被遍历完这棵树（root不为空 或入栈的未处理完）
        while (root != null || !stack.isEmpty()){
            // 左：先一路向左入栈
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            // 右：右节点不为空并且未被访问过，才能入栈遍历它（再次左右中，先左）
            //从栈顶节点（就是从最底层的最左的节点）开始遍历
            TreeNode node = stack.peek();
            if(node.right !=null && node.right != prev){
                // 右结点还没遍历，遍历右结点
                //stack.push(node.right);  //与下一行重复了
                root = node.right; //使得root不为空，会在while循环里入栈
            }else {
                //否则右节点空 || 被访问过， 当前节点已经被遍历过
                //getHeight第一次传的时候，node是叶子节点，node.left为null
                if(Math.abs(getHeight(node.left) - getHeight(node.right)) > 1)
                    return false;// 不是高度平衡的二叉树(左右子树的高度差 >1)

                // 中：当前节点已经被遍历过，就出栈
                stack.pop();
                root = null;//null表示不用再一路向左遍历了
                prev = node;
            }
        }
        //全遍历后
        return true;
    }
    //求高度的方法1：
    //优化迭代法，对暴力迭代法的方法做优化，
    // 利用TreeNode.val来保存当前结点的高度，这样就不会有重复遍历，
    // 使得获取高度算法时间复杂度可以降到O(1)，总的时间复杂度降为O(n)。
    private int getHeight(TreeNode root){
        // getHeight第一次传的时候，node是叶子节点，node.left为null
        if(root == null) return 0;
        int leftHeight = root.left ==null? 0:root.left.val;
        int rightHeight = root.right == null? 0 : root.right.val;
        int height = Math.max(leftHeight,rightHeight) +1;
        //先保存当前节点的高度
        root.val = height;
        return height;
    }
    //求高度的方法2：
    // 层序遍历，求结点的高度(遍历一层就 加1个高度)
    private int getHeight1(TreeNode root){
        if(root == null) return 0;
        // 层序遍历就用队列呀
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//初始
        int depth = 0;//初始化

        while (!queue.isEmpty()){
            int size = queue.size();//队列存的这一层的元素、也是需要遍历的元素个数
            ++depth;
            while (size >0 ){ //处理队列中存的这一层节点
                TreeNode node = queue.poll();//一个一个出队进行处理
                if(node.left != null) queue.offer(node.left);//先进后出嘛，现在入队在node这一层的后面呢。
                // 把node父节点的这一层的元素处理完，才会在下一层处理处理到node.left等等子节点这一层
                if(node.right != null) queue.offer(node.right);
                --size;
            }
        }
        return depth;
    }
}

    //目标：判断它是否是高度平衡的二叉树(左右子树的高度差 <=1)
    class Solution110 {
        //高度要后序遍历：左右中：从叶子节点的高度为1开始
        // 递归法：计算高度(同时判断高度差)
        public boolean isBalanced(TreeNode root) {
            return getHeight(root) != -1; // -1是false
        }
        // 递归法：
        //1、确定递归参数与返回值，参数：root节点；返回值是高度 int(或者高度差>1返回-1)
        //2、递归终止条件：root为空、高度为-1
        //3、递归的单层处理：
        //高度差>1就用-1标记； 左右子树的高度差<=1 的就正常返回高度
        private int getHeight(TreeNode root){
            if(root == null) return 0;
            // root.left可以为null，因为递归后会=0
            //终止条件2
            int leftheight = getHeight(root.left);//左
            if(leftheight == -1) return -1;

            int rightheight = getHeight(root.right);//右
            if(rightheight == -1) return -1;

            //中
            if(Math.abs(leftheight - rightheight) > 1){
                return -1; // 左右子树的高度差 >1 不平衡了，-1表示不是平衡的树了
            }
            //正常返回高度（此节点root的高度=左右子树的高度的最大值 + 1(根节点root的高)）
            return Math.max(leftheight, rightheight) + 1;
        }

    }


// 利用特性。
// 完全二叉树的子树、递归后至少有颗是满二叉树 （1 直接是满的；
// （2 不满但子树即使只是1个节点也算是满的、其他情况是>2层的、肯定有满的）
// 满二叉树好计算（2 ^ 深度-1），那怎样是？——递归向左遍历=递归向右遍历的深度
class Solution222 {
    // 递归法实现
    public int countNodes(TreeNode root) {
        // 1、递归参数、返回值：ok
        // 2、递归终止条件: // 3、底层的单层处理逻辑
        if(root == null ) return 0;
        // 满二叉树可以直接计算、也可以终止。
        // 判断满二叉树：求深度 直接指针++就OK
        int leftDepth = 0, rightDepth = 0;
        TreeNode left = root.left;
        TreeNode right = root.right;

        while (left !=null) {
            left = left.left;
            leftDepth++;
        }
        while (right !=null) {
            right = right.right;
            rightDepth++;
        }

        if(leftDepth == rightDepth)
            return (1 << (leftDepth +1)) -1;// 1 * 2 ^(leftDepth +1) -1
        //左移：m << n表示 m 乘以2的n次方
//返回：2 ^ depth -1，其中树的深度是leftDepth +1 （因为leftDepth是根节点的子树的高度）
        //节点个数：根+两个子树。
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}



// 二叉树的最小深度
// 找叶子节点（只有当左右孩子都为空的时候，才说明遍历的最低点了）
// 如果其中一个孩子为空则不是最低点
// 使用迭代法 进行层次遍历，一层一层的找，总能先找到叶子。
class Solution111 {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;  //因为这里的node可能为0
        // 层次遍历树、用队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int deep = 0;//初始化
        while (!queue.isEmpty()){
            int size = queue.size();
            ++deep;
            while (size > 0){//处理这一层
                TreeNode node = queue.poll();
                // 先判断是叶子节点？
                if(node.left == null && node.right == null) return deep;
                //不是的话，就正常遍历了
                if(node.left !=null) queue.offer(node.left);
                if(node.right !=null) queue.offer(node.right);
                --size;
            }

        }
        //即使是满二叉树、上面就return deep了
        return deep;
    }
}


//二叉树的最大深度
// 使用迭代法的话，最大的深度就是二叉树的层数，使用层序遍历
//在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，
class Solution104_1 {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int deep = 0;
        // 树的层次遍历、使用队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//第一层 根节点入队
        while (!queue.isEmpty()){
            int size = queue.size(); //队列不为空、直接处理这一层while
            ++deep;
            while (size >0){
                TreeNode node = queue.poll();
                if (node.left !=null) queue.offer(node.left);//从左到右存节点的下一层
                if (node.right !=null) queue.offer(node.right);
                --size;
            }
        }
        return deep;

    }
}


class Solution102_1 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //二叉树的层序遍历——迭代法
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res; //树节点为空时
        // 一旦出现树的层次遍历，都可以用队列作为辅助结构
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 初始：根节点入队
        //队列先进先出，则当前层节点一定会被优先访问。
        // 弹出当前层节点的同时依次加入下一层节点。
        while (!queue.isEmpty()){
            // size：队列中存的 当前层节点数量。
            // size 二叉树这一层有多少元素,队列就弹出几个元素。
            int size = queue.size();
            List<Integer> resLevel = new ArrayList<>();// 存 当前层遍历结果
            for (int i =0; i < size; i++){
                TreeNode node = queue.poll(); //队列弹出元素，先进先出（是从左到右顺序的）
                resLevel.add(node.val);
                // 弹出当前层节点的同时依次加入下一层节点。
                if (node.left !=null)  queue.offer(node.left); //进队列，处理下层时再出队。
                if (node.right !=null)  queue.offer(node.right);
            }
            //这一层遍历完，就存这层结果
            res.add(resLevel);
        }
        return res;
    }
}


class Solution44 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        // while 循环控制从上向下一层层遍历
        while (!q.isEmpty()) {
            int sz = q.size();
            // 记录这一层的节点值
            List<Integer> level = new LinkedList<>();
            // for 循环控制每一层从左向右遍历
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                level.add(cur.val);
                if (cur.left != null)
                    q.offer(cur.left);
                if (cur.right != null)
                    q.offer(cur.right);
            }
            res.add(level);
        }
        return res;
    }
}

//    List<Integer> res = new ArrayList<>(); //存放结果集
//    public List<Integer> postorderTraversal(TreeNode root) {
//        traverse(root);
//        return res;
//    }
//    // 递归函数 ，遍历二叉树所有 节点
//    //后序遍历：左右中
//    private void traverse(TreeNode root) {//确定递归函数的参数和返回值
//        if (root == null)
//            return;//递归终止条件
//
//        // 单层递归的逻辑
//        traverse(root.left);
//        traverse(root.right);
//        res.add(root.val);
//    }

class Solution333 {
    //后序遍历顺序：左右中
    //所以需要使得：入栈顺序：中左右，出栈的顺序就是：中右左， 最后翻转结果就是左右中（就是后序遍历顺序了）。
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); //存放结果集
        if (root == null)
            return res;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){//遍历
            // 需要使得：入栈顺序：中左右
            TreeNode node = stack.pop(); //后进先出，从栈中取 node
            res.add(node.val);

            if (node.left !=null){
                stack.push(node.left);
            }
            if (node.right !=null){
                stack.push(node.right);
            }
        }
        // 需要将出栈的顺序中右左，翻转成左右中
        Collections.reverse(res);
        return res;
    }
}


class Solution22 {
    //中序遍历：处理顺序和访问顺序是不一致的。
    //栈记录：记录指针遍历途中访问过的节点（待处理），处理谁就弹出谁
    //指针：遍历二叉树、要处理谁
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); //存放结果集
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 一路向左入栈直到为NULL，弹出栈元素top并加入res结果集，
        // 若top无右节点则接着弹出，若有则将其入栈并开始下一循环。
        while (cur !=null || !stack.isEmpty()){//遍历结束条件
            if (cur !=null){
                stack.push(cur); // 一路向左入栈直到为NULL
                cur = cur.left;  // 中序遍历: 左中右
            }else {
                // 当指针为null时，就要从栈里弹出最近访问过的节点进行处理了。
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right; // 处理右子树，左中已经访问处理过了
            }
        }
        return res;
    }
}

class Solution123 {  //迭代遍历

//标记要处理的节点——就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 （标记法）
// 后序遍历顺序：左右中
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>(); //存放结果集
    if (root == null)
        return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root); // 初始：根节点入栈

    while (!stack.isEmpty()) { //迭代法后序遍历
        // 需要使得：入栈顺序：中右左
        TreeNode node = stack.peek();
        if (node != null) { // node 为null 是标记节点，排除这种情况
            stack.pop();//重要！！！该节点已经正在被处理了，需要将该节点弹出。
            stack.push(node);
            //在访问过但是还没有处理的、之后需要处理的节点后面放入空节点 作为标记
            stack.push(null);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        } else {
            //栈不为空并且 node 为null 的标记，下一个就是要处理的节点了。
            stack.pop();//去除标记节点
            res.add(stack.pop().val);
        }
    }
    return res;
}

//标记要处理的节点——就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 （标记法）
// 中序遍历顺序：左中右
// 迭代法中序遍历。
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>(); //存放结果集
    if (root == null)
        return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root); // 初始：根节点入栈

    while (!stack.isEmpty()){
        TreeNode curNode = stack.peek();

        if(curNode !=null){  // 处理此节点：入栈顺序：右中左
            stack.pop(); //该节点已经正在被处理，将该节点弹出，换成了将来处理它的右中左节点，添加到栈中
            if (curNode.right !=null) stack.push(curNode.right);
            stack.push(curNode);
            // 中节点访问过，但是还没有处理（按照出栈时的左中右顺序才能处理、放入结果集中），加入空节点做为标记。
            stack.push(null);
            if (curNode.left !=null) stack.push(curNode.left);
        }else{
            // 为空，说明下一个节点就是要处理的节点了。
            stack.pop(); // 去除做为标记的空节点
            //处理
            res.add(stack.pop().val);
        }
    }
    return res;
}


    // 将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
    //标记要处理的节点——就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 （标记法）
    // 前序遍历顺序：中-左-右
    // 迭代法前序遍历。
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); //存放结果集
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root); // 初始：根节点入栈

        while (!stack.isEmpty()){ //迭代遍历
            TreeNode node = stack.peek(); //从栈顶开始处理
            if (node !=null){  // node 为null 是标记节点，排除这种情况
                stack.pop();//该节点已经正在被处理，将该节点弹出，避免重复操作
                if (node.right !=null) stack.push(node.right); // 入栈顺序：右左中
                if (node.left !=null) stack.push(node.left);
                stack.push(node);
                //标记要处理的节点——就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。
                stack.push(null);
            }else {
                // 栈不为空并且 node 为null 的是标记节点，
                // 只有遇到空节点的时候，才将下一个节点(要处理的节点)放进结果集
                stack.pop(); //去除标记节点
                res.add(stack.pop().val);
            }
        }
        return res;
    }
}

class Solution11 { //前序遍历 ：迭代遍历
    // 前序遍历顺序：中-左-右，入栈顺序：中-右-左
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); //存放结果集
        //树中节点数目在范围 [0, 100] 内
        if (root == null)
            return res;
        // 用栈 实现二叉树的前后中序遍历
        Stack<TreeNode> stack = new Stack<>(); // 入栈顺序：中-右-左
        stack.push(root); // 初始：根节点入栈
        while (!stack.isEmpty()){
            TreeNode node = stack.pop(); //后进先出，从栈中取 node
            res.add(node.val); // 入栈：中
            // 入栈顺序：中-右-左
            if (node.right !=null)
                stack.push(node.right); // 入栈：右
            if (node.left !=null)
                stack.push(node.left); // 入栈：左
        }

        return res;
    }
}

//    List<Integer> res = new ArrayList<>();
//    public List<Integer> preorderTraversal(TreeNode root) {
//        traverse(root);
//        return res;
//    }
//    // 遍历函数 ，遍历二叉树所有 节点
//    // 前序遍历某个节点：第一个是根节点的值，接着是左子树，最后是右子树
//    private void traverse(TreeNode root){//确定递归函数的参数和返回值
//
//        if (root == null) return;
//
//        res.add(root.val);
//        traverse(root.left);
//        traverse(root.right);
//    }




    /* 动态规划思路 */
    // 定义：输入一个节点，返回以该节点为根的二叉树的前序遍历结果
    public List<Integer> preorderTraversal1(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        // 前序遍历结果特点：第一个是根节点的值，接着是左子树，最后是右子树
        res.add(root.val);
        res.addAll(preorderTraversal1(root.left));
        res.addAll(preorderTraversal1(root.right));
        return res;
    }

    /* 回溯算法思路 */
    LinkedList<Integer> res22 = new LinkedList<>();
    // 返回前序遍历结果
    public List<Integer> preorderTraversal2(TreeNode root) {
        traverse22(root);
        return res22;
    }
    // 二叉树遍历函数
    void traverse22(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序遍历位置
        res22.add(root.val);
        traverse22(root.left);
        traverse22(root.right);
    }

}